
///这个函数必须是单形

static inline int is_edge_legacy_to_collapse(Mesh* m,template_f* f)
{
    Node*n1=m->vv_begin(m,*(f->vertices[0]));
    for(int i=1;i<f->vertices_size;i++)
    {
        if(n1==NULL){break;}
        Node* n2=m->vv_begin(m,*(f->vertices[i]));
        Node* n=node_intersection(n1,n2);
        free_node(n1);free_node(n2);
        n1=n;
    }
    int size= node_size(n1);
    free_node(n1);
    return size;
}

// M 是rows个顺序点的坐标
static double* my_deault_compute_normal(double ** M,int rows,LB_Matrix* mat)
{
    double* re=(double*)malloc(sizeof(double)*rows);
    // LB_Matrix* mat=(LB_Matrix*)malloc(sizeof(LB_Matrix));
    // lb_matrix_init_double(mat,rows-1,rows-1);
    double* data=(double*)(mat->data);
    for(int k=0;k<rows;k++)
    {
        int temp_j=0;
        for(int j=0;j<rows;j++)
        {
            if(j==k){continue;}
            for(int i=0;i<rows-1;i++)
            {
                data[i*(rows-1)+temp_j]=M[i+1][j]-M[0][j];
            }
            temp_j++;
        }
        double * det=(double*)(mat->det(mat));
        re[k]=*det;
        (k%2==1)?(re[k]=-re[k]):(re[k]=re[k]);
        free(det);
    }
    //lb_matrix_free(mat);
    return re;
}

static double* my_deault_compute_normaln(template_v** cvs,int rows,LB_Matrix* mat)
{
    double* re=(double*)malloc(sizeof(double)*rows);
   
    double* data=(double*)(mat->data);
    for(int k=0;k<rows;k++)
    {
        int temp_j=0;
        for(int j=0;j<rows;j++)
        {
            if(j==k){continue;}
            for(int i=0;i<rows-1;i++)
            {
                data[i*(rows-1)+temp_j]=cvs[i+1]->point[j]-cvs[0]->point[j];
            }
            temp_j++;
        }
        double * det=(double*)(mat->det(mat));
        re[k]=*det;
        (k%2==1)?(re[k]=-re[k]):(re[k]=re[k]);
        free(det);
    }
    return re;
}

static template_v*  my_is_two_halffaces_connected(template_v* hfvs1,template_v* hfvs2,int len)
{
    template_v* re=NULL;
    for(int i=0;i<len;i++)
    {
        int flag=0;
        for(int j=0;j<len;j++)
        {
            if(hfvs1[i]==hfvs2[j]){flag=1;break;}
        }
        if(flag==0)
        {
            if(re==NULL){re=hfvs1[i];}
            else{return NULL;}
        }
    }
    return re;
}


static template_v*  my_is_two_halffaces_connectedn(template_hf* hf1,template_hf* hf2)
{
    if(hf1==hf2){return NULL;}
    return  my_is_two_halffaces_connected(hf1->vertices,hf2->vertices,hf1->vertices_size);
}


static int my_is_vertex_in_cell(template_v* cvs,int size ,template_v*v)
{
    for(int i=0;i<size;i++)
    {
        if(cvs[i]==v){return 0;}
    }
    LB_Matrix* mat =(LB_Matrix*)malloc(sizeof(LB_Matrix));
    lb_matrix_init_double(mat,size-1,size-1);
    int cols=cvs[0]->point_size;

    auto my_get_vertexp[cvs,v](int i,int j){return i==j?(v->point):(cvs[j]->point); };
    int re=1;
    if(cols==size-1)
    {
        double* data=(double*)(mat->data);
        double* inns=(double*)malloc(sizeof(double)*size);
        memset(inns,0,sizeof(double)*size);
        for(int k=0;k<size;k++)
        {
            double *p0=my_get_vertexp(k,0);
            for(int i=0;i<cols;i++)
            {
                double*  pi=my_get_vertexp(k,i+1);
                for(int j=0;j<cols;j++)
                {
                    data[i*cols+j]=pi[j]-p0[j];
                }
            }
            double* det=mat->det(mat);
            inns[k]=*det;
            free(det);
        }
        for(int i=1;i<size;i++)
        {
            if(inns[i]*inns[0]<0)
            {
                re=0;break;
            }
        }
        free(inns);
    }
    else if(cols==size)
    {
        double **M=(double**)malloc(sizeof(double*)*size);
        double* normals=(double**)malloc(sizeof(double*)*size);
        for(int k=0;k<size;k++)
        {
            for(int i=0;i<size;i++)
            {
                M[i]=my_get_vertexp(k,i);
            }
            normals[k]=my_deault_compute_normal(M,size,mat);
        }
        for(int i=0;i<size-1;i++)
        {
            for(int j=i+1;j<size;j++)
            {
                if(inner_product(normals[i],normals[j],size)<0)
                {
                    re=0;break;
                }
            }
            if(re==0){break;}
        }
        for(int i=0;i<size;i++)
        {
            free(normals[i]);
        }
        free(M);
    }
    lb_matrix_free(mat);
    return re;
}


static int my_panduan_cell_is_legal(double**M,int rows, double* normal,int cols,
    LB_Matrix* mat)
{
    int re=1;
    if(rows-1==cols)
    {
        double* data=(double*)(mat->data);
        for(int i=0;i<cols;i++)
        {
            for(int j=0;j<cols;j++)
            {
                data[i*cols+j]=M[i+1][j]-M[0][j];
            }
        }
        double* det=mat->det(mat);
        if(*det<0){re=0;}
        free(det);
        
    }
    else if(rows==cols)
    {
        if(normal==NULL){return 1;}

        double* nor=my_deault_compute_normal(M,cols,mat);
        if(inner_product(nor,normal,cols)<0)
        {
            re=0;
        }
        SAFE_FREE(nor);
    }
    return re;
}

static int my_panduan_cell_is_legaln(template_v**cvs,int rows, double* normal,int cols,
    LB_Matrix* mat)
{
    int re=1;
    if(rows-1==cols)
    {
        double* data=(double*)(mat->data);
        for(int i=0;i<cols;i++)
        {
            for(int j=0;j<cols;j++)
            {
                data[i*cols+j]=cvs[i+1]->point[j]-cvs[0]->point[j];
            }
        }
        double* det=mat->det(mat);
        if(*det<0){re=0;}
        free(det);
        
    }
    else if(rows==cols)
    {
        if(normal==NULL){return 1;}

        double* nor=my_deault_compute_normaln(cvs,cols,mat);
        if(inner_product(nor,normal,cols)<0)
        {
            re=0;
        }
        SAFE_FREE(nor);
    }

    return re;
}
static Int_RB_Tree * my_get_all_illegal_halffaces(Int_RB_Tree* tree_hf,
    double * p,double* normal,int cols)
{
    if(tree_hf->size<=0){return NULL;}
    Int_RB_Tree * re=(Int_RB_Tree*)malloc(sizeof(Int_RB_Tree));
    int_rb_tree_init(re);
    auto it=tree_hf->begin(tree_hf);
    template_hf* hf=(template_hf*)(it.second);
    double **M=(double**)malloc(sizeof(double*)*(hf->vertices_size+1));
    M[hf->vertices_size]=p;
    LB_Matrix* mat =(LB_Matrix*)malloc(sizeof(LB_Matrix));
    lb_matrix_init_double(mat,hf->vertices_size,hf->vertices_size);
    for(;it.it!=NULL;it++)
    {
        hf=(template_hf*)(it.second);
        for(int i=0;i<hf->vertices_size;i++)
        {
            M[i]=hf->vertices[i]->point;
        }
        if(my_panduan_cell_is_legal(M,hf->vertices_size+1,normal,cols,mat)==0)
        {
            re->insert(re,hf->id,hf);
            tree_hf->erase(tree_hf,hf->id);
        }
    }
    
    lb_matrix_free(mat);
    free(M);
    return re;
}


static Int_RB_Tree* my_get_all_connneted_halffaces(Int_RB_Tree* tree_hf,template_hf*hf,Int_RB_Tree* re)
{
    for(auto it=tree_hf->begin(tree_hf);it.it!=NULL;it++)
    {
        template_hf* hf1=(template_hf*)(it.second);
        template_v*v=my_is_two_halffaces_connectedn(hf1,hf);
        if(v!=NULL)
        {
            re->insert(re,hf1->id,v);
        }
    }
    return re;
}

static int my_is_halfface_is_in_cell(template_hf*hf, template_v** cvs,int rows)
{
    for(int i=0;i<hf->vertices_size;i++)
    {
        int flag=0;
        for(int j=0;j<rows;j++)
        {
            if(hf->vertices[i]==cvs[j]){flag=1;break;}
        }
        if(flag==0){return 0;}
    }
    return 1;
}
static int my_is_hfvs_equal_halfface(template_v**hfvs,template_hf* hf)
{
    int re=1;
    Node*node=NULL
    for(int i=0;i<hf->vertices_size;i++)
    {
        node=node_overlying(node,hf->vertices[i]);
    }
    for(int i=0;i<hf->vertices_size;i++)
    {
        Node* nit=node_find(node,hfvs[i]);
        if(nit==NULL)
        {   re=0;
            break;}
        node=node_remove(node,nit);
    }
    free_node(node);

    return 1;
}

static template_hf* my_find_halffacep(template_v**hfvs,Int_RB_Tree* tree_hf)
{
    for(auto it=tree_hf;it.it!=NULL;it++)
    {
        template_hf *hf=(template_hf*)(it.second);
        if(my_is_hfvs_equal_halfface(hfvs,hf)==1)
        {
            return hf;
        }
    }
    return NULL;
}



static Node* my_chuli_cell(Node* node_c, Int_RB_Tree* tree_hf,Int_RB_Tree*tree_hf1,template_c*c,
    template_v* nv,double*normal,int cols,LB_Matrix* mat)
{
    int size=c->vertices_size;
    //template_v**hfvs=(template_v**)malloc(sizeof(template_v*)*(size-1));
    template_v**cvs=(template_v**)malloc(sizeof(template_v*)*size);
    cvs[size-1]=nv;
    for(int i=0;i<size;i++)
    {
        int temp_i=0;
        for(int j=0;j<size;j++)
        {
            if(j!=i)
            {
                cvs[temp_i]=c->vertices[j];
                temp_i++;
            }
        }
        if((size-i-1)%2==0)
        {}
        else if(size>2)
        {
            template_v* vv=cvs[0];
            cvs[0]=cvs[1];
            cvs[1]=vv;
        }
        template_hf*hf= my_find_halffacep(cvs,tree_hf);
        if(hf==NULL)
        {
            hf=my_find_halffacep(cvs,tree_hf1);
            if(hf==NULL)
            {
                hf=(template_hf*)malloc(sizeof(template_hf));
                HalfFace_init_(hf);
                hf->id;

                if(my_panduan_cell_is_legaln(cvs,size,normal,cols,mat))
                {
                    tree_hf->insert(tree_hf,)
                }
                else
                {

                }
            }
            else{
                tree_hf1->erase(tree_hf1,hf->id);
            }

        }
        else
        {
            tree_hf->erase(tree_hf,hf->id);
        }
    }
    free(cvs);
    //free(hfvs);

    return node_c;

}

static Int_RB_Tree* my_get_cells_from_halffaces(Int_RB_Tree* tree_hf,
    template_v*v,double* normal,int cols)
{
    Int_RB_Tree* tree_hf1=my_get_all_illegal_halffaces(tree_hf,
        v->point,normal,cols);
    // Int_RB_Tree* tree_c=(Int_RB_Tree*)malloc(sizeof(Int_RB_Tree));
    // int_rb_tree_init(tree_c);
    Node* cells=NULL;

    if(tree_hf1!=NULL)
    {
        int rows=hf->vertices_size+1;
        template_v**cvs=(template_v**)malloc(sizeof(template_v*)*rows);
        //double **M=(double**)malloc(sizeof(double*)*rows);
        //M[hf->vertices_size]=p;
        LB_Matrix* mat =(LB_Matrix*)malloc(sizeof(LB_Matrix));
        lb_matrix_init_double(mat,hf->vertices_size,hf->vertices_size);
        int flag=1;
        while(flag)
        {
            flag=0;
            for(auto it= tree_hf1->begin(tree_hf1);it.it!=NULL;it++)
            {
                template_hf* hf=(template_hf*)(it.second);
                for(int i=0;i<hf->vertices_size;i++)
                {
                    cvs[i]=hf->vertices[i];
                }
                Int_RB_Tree* tree_con_hf=(Int_RB_Tree*)malloc(sizeof(Int_RB_Tree));
                int_rb_tree_init(tree_con_hf);
                tree_con_hf=my_get_all_connnetex_halffaces(tree_hf,hf,tree_con_hf);
                tree_con_hf=my_get_all_connnetex_halffaces(tree_hf1,hf,tree_con_hf);
                for(auto it1=tree_con_hf->begin(tree_con_hf);it1.it!=NULL;it1++)
                {
                    template_v*v=(template_v*)(it1.second);

                    M[hf->vertices->size]=v;
                    if(my_panduan_cell_is_legaln(cvs,rows,normal,cols,mat))
                    {
                        flag=1;

                        // tree_hf1->erase(tree_hf1,hf->id);
                        // tree_hf1->erase(tree_hf1,it1.first);
                        // tree_con_hf->erase(tree_con_hf,it1.first);
                        break;
                    }
                }


                int_rb_tree_free(tree_con_hf);
                if(flag){break;}
            }
        }
        lb_matrix_free(mat);
        free(cvs);
        //free(M);
    }


    return tree_c;
}

template_v*  collapse_edge(Mesh* m,template_f* f ,double* p,double* normal)
{
    Int_RB_Tree* tree_c=(Int_RB_Tree*)malloc(sizeof(Int_RB_Tree));
    int_rb_tree_init(tree_c);
    for(int i=0;i<f->vertices_size;i++)
    {
        for(Node* nit=f->vertices[i]->cells;nit!=NULL;nit=(Node*)(nit->Next))
        {
            template_c* c=(template_c*)(nit->value);
            tree_c->insert(tree_c,c->id,c);
        }    
    }
    //Node* bound_hfs=is_edge_legacy_to_collapse(m,f,tree_c);
    Int_RB_Tree* tree_hf=(Int_RB_Tree*)malloc(sizeof(Int_RB_Tree));
    int_rb_tree_init(tree_hf);
    for(auto it=tree_c->begin(tree_c);it.it!=NULL;it++)
    {
        template_c* c=(template_c*)(it.second);
        for(auto chfit=m->chf_begin(m,*c);chfit!=m->chf_end(m,*c);chfit++)
        {
            template_hf* hf=quote(chfit);

            template_hf*hf1=(template_hf*)(tree_hf->find(tree_hf,hf->face->id));
            if(hf1==NULL )
            {
                //vs=(template_v**)malloc(sizeof(template_v*)*hf->vertices_size);
                hf1=(template_hf*)malloc(sizeof(template_hf));
                HalfFace_init_(hf1);

                hf1->vertices_size=hf->vertices_size;
                hf1->vertices=(template_v**)malloc(sizeof(template_v*)*hf->vertices_size);
                hf1->id=hf->face->id;
                memmove(hf1->vertices,hf->vertices,sizeof(template_v*)*hf->vertices_size);
                tree_hf->insert(tree_hf,hf1->id,hf1);
            }
            else
            {
                free_HalfFace(hf1);
                tree_hf->erase(tree_hf,hf1->id);
            }
        } 
    }

    template_v*re=m->create_vertexv(m,p,3);






    //free_node(bound_hfs);
    int_rb_tree_free(tree_hf);
    int_rb_tree_free(tree_c);
    return re;
}